public class QuickSort {

    // 主函数，用于测试
    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        int n = array.length;

        QuickSort ob = new QuickSort();
        ob.sort(array, 0, n-1);

        System.out.println("Sorted array:");
        printArray(array);
    }

     static void sort(int[]array,int low,int high){
        if (low < high){
            int pos = partion(array,low,high);
            sort(array, low, pos-1);
            sort(array, pos+1, high);
        }
     }

    static int partion(int[]array,int low,int high){
        int low_pos = low-1;
        int pos = high;
        for(int j = low;j<high;j++){
            if(array[j]<array[pos]){
                low_pos++;
                int tmp = array[j];
                array[j] = array[low_pos];
                array[low_pos] = tmp;
            }
        }
        int tmp = array[low_pos+1];
        array[low_pos+1] = array[pos];
        array[pos] = tmp;
        return low_pos+1;
    }


    // 打印数组函数
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
}